/*
 * @Author: your name
 * @Date: 2024-04-16 14:43:12
 * @LastEditTime: 2024-04-17 10:01:48
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\239.滑动窗口最大值.cpp
 */
/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
// class Solution {
// public:
//     class MyQueue{
//         deque<int> que;
//     public:
//         void pop(int val){
//             if(!que.empty() && que.front() == val)
//                 que.pop_front();
//         }

//         void push(int val){
//             while(!que.empty() && que.back() < val){
//                 que.pop_back();
//             }
//             que.push_back(val);
//         }
//         int front(){
//             return que.front();
//         }
//     };


//     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//         MyQueue que;
//         vector<int> res;
//         for(int i = 0; i< k; i++){
//             que.push(nums[i]);
//         }
//         res.push_back(que.front());
//         for(int i = k; i < nums.size()-k; i++){
//             que.pop(nums[i-k]);
//             que.push(nums[i]);
//             res.push_back(que.front());
//         }
//         return res;
//     }
// };

class Solution {
private:
    class MyQueue { //单调队列（从大到小）
    public:
        deque<int> que; // 使用deque来实现单调队列
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        // 同时pop之前判断队列当前是否为空。
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};
// @lc code=end

// 重要！！